from collections import deque
import numpy as np

# 优化版本：合并状态压缩
def solve_maze_combined_state(maze, coin_value=5, trap_penalty=-3, boss_penalty=-1, locker_penalty=-7):
    """
    使用单一位掩码同时记录金币和陷阱状态的优化版本
    """
    rows = len(maze)
    cols = len(maze[0])
    
    # 收集所有关键位置
    start = None
    end = None
    items = []  # 统一存储金币和陷阱
    item_types = {}  # 记录每个物品的类型
    
    for i in range(rows):
        for j in range(cols):
            if maze[i][j] == 'S':
                start = (i, j)
            elif maze[i][j] == 'E':
                end = (i, j)
            elif maze[i][j] == 'G':
                items.append((i, j))
                item_types[(i, j)] = 'coin'
            elif maze[i][j] == 'T':
                items.append((i, j))
                item_types[(i, j)] = 'trap'
            elif maze[i][j] == 'B':
                items.append((i, j))
                item_types[(i, j)] = 'boss'
            elif maze[i][j] == 'L':
                items.append((i, j))
                item_types[(i, j)] = 'locker'
    
    item_map = {item: idx for idx, item in enumerate(items)}
    num_items = len(items)
    print(num_items)
    
    print(f"总共 {num_items} 个物品（金币+陷阱）")
    
    # 状态：(位置, 物品状态掩码)
    dp = {}
    parent = {}
    
    queue = deque([(start, 0, 0)])  # (位置, 状态掩码, 当前价值)
    dp[(start[0], start[1], 0)] = 0
    
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_value_at_end = float('-inf')
    best_end_state = None
    
    step_count = 0
    max_steps = 50000
    
    # while queue and step_count < max_steps:
    while queue:
        step_count += 1
        (x, y), item_mask, current_value = queue.popleft()
        
        if (x, y) == end:
            if current_value > max_value_at_end:
                max_value_at_end = current_value
                best_end_state = (x, y, item_mask)
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] != '#':
                new_mask = item_mask
                new_value = current_value
                
                # 检查是否是特殊物品
                if (nx, ny) in item_map:
                    item_idx = item_map[(nx, ny)]
                    if not (item_mask & (1 << item_idx)):  # 第一次接触
                        new_mask |= (1 << item_idx)
                        if item_types[(nx, ny)] == 'coin':
                            new_value += coin_value
                        elif item_types[(nx, ny)] == 'trap':
                            new_value += trap_penalty
                
                state = (nx, ny, new_mask)
                if state not in dp or dp[state] < new_value:
                    dp[state] = new_value
                    parent[state] = (x, y, item_mask)
                    queue.append(((nx, ny), new_mask, new_value))
    
    # 回溯路径
    if best_end_state:
        path = []
        current = best_end_state
        while current in parent:
            path.append((current[0], current[1]))
            current = parent[current]
        path.append(start)
        path.reverse()
        
        # 分析路径收益
        total_value = analyze_path_gains(path, maze, items, item_types, coin_value, trap_penalty, boss_penalty, locker_penalty)
        
        return total_value, path
    
    return float('-inf'), []

def analyze_path_gains(path, maze, items, item_types, coin_value, trap_penalty, boss_penalty=-1, locker_penalty=-7):
    """分析路径中的收益详情"""
    total_coins = 0
    total_traps = 0
    total_bosses = 0
    total_lockers = 0
    collected_items = set()
    
    print("\n=== 路径分析 ===")
    for i, (x, y) in enumerate(path):
        if (x, y) in item_types and (x, y) not in collected_items:
            collected_items.add((x, y))
            if item_types[(x, y)] == 'coin':
                total_coins += 1
                print(f"步骤 {i}: 在({x},{y})收集金币 +{coin_value}")
            elif item_types[(x, y)] == 'trap':
                total_traps += 1
                print(f"步骤 {i}: 在({x},{y})踩到陷阱 {trap_penalty}")
            elif item_types[(x, y)] == 'boss':
                total_bosses += 1
                print(f"步骤 {i}: 在({x},{y})踩到boss {boss_penalty}")
            elif item_types[(x, y)] == 'locker':
                total_lockers += 1
                print(f"步骤 {i}: 在({x},{y})踩到locker {locker_penalty}")
                
    total_value = total_coins * coin_value + total_traps * trap_penalty + total_bosses * boss_penalty + total_lockers * locker_penalty
    print(f"\n总收益: {total_coins}金币({total_coins * coin_value}) + {total_traps}陷阱({total_traps * trap_penalty}) + {total_bosses}boss({total_bosses * boss_penalty}) + {total_lockers}locker({total_lockers * locker_penalty}) = {total_value}")
    return total_value

# 可视化增强版
def visualize_path_enhanced(maze, path):
    """增强的路径可视化"""
    import copy
    visual_maze = copy.deepcopy(maze)
    
    # 标记路径
    for i, (x, y) in enumerate(path):
        if visual_maze[x][y] == ' ':
            visual_maze[x][y] = '.'
        elif visual_maze[x][y] == 'S':
            visual_maze[x][y] = 'S'  # 保持起点标记
        elif visual_maze[x][y] == 'E':
            visual_maze[x][y] = 'E'  # 保持终点标记
    
    print("\n=== 迷宫路径可视化 ===")
    print("图例: S=起点, E=终点, G=金币, T=陷阱, .=路径, #=墙壁")
    for row in visual_maze:
        print(' '.join(f'{cell:>2}' for cell in row))

# 测试
if __name__ == "__main__":
    maze = [
    ["#","E","#","#","#","#","#","#","#","#","#","#","#","#","#"],
    ["#"," "," ","B"," "," "," "," "," "," ","#"," "," "," ","#"],
    ["#","#","#"," ","#"," ","#","#","#","#","#","#","#"," ","#"],
    ["#"," "," ","T","#"," "," ","G"," "," ","#"," "," "," ","#"],
    ["#"," ","#","#","#"," ","#","#","#","#","#","#","#"," ","#"],
    ["#"," "," "," ","#"," "," "," ","#"," ","#"," "," "," ","#"],
    ["#","#","#"," ","#"," ","#"," ","#"," ","#","#","#"," ","#"],
    ["#"," "," "," ","#"," ","#"," "," "," "," "," ","#"," ","#"],
    ["#","#","#","#","#"," ","#","#","#","#","#","L","#"," ","#"],
    ["#"," ","#","G","#"," "," ","G","#"," ","#"," "," "," ","#"],
    ["#"," ","#"," ","#"," ","#"," ","#"," ","#"," ","#","#","#"],
    ["#"," ","#"," ","#"," ","#","T"," "," ","#"," "," "," ","#"],
    ["#"," ","#"," ","#"," ","#","#","#"," ","#"," ","#","#","#"],
    ["#"," "," "," "," ","T"," "," ","#"," ","#"," "," "," ","#"],
    ["#","#","#","#","#","#","#","#","#","#","#","#","#","S","#"]
  ]
    
    print("=== 使用合并状态压缩求解 ===")
    max_value, path = solve_maze_combined_state(maze, coin_value=5, trap_penalty=-3)
    print(f"\n最大收益: {max_value}")
    print(f"路径长度: {len(path)}")
    print(path)
    
    if path:
        visualize_path_enhanced(maze, path)
